<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
	
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
	<!-- Icona Neptune info at www.convertico.com -->
	<link type="image/x-icon" rel="Shortcut Icon" href="img/neptune.ico">
	<title>Neptune - Info about allocation process</title>
</head>

<body style="margin:0px; background-color: #FFFFFF; font-family: helvetica;">
<table  border="0" cellpadding="0" cellspacing="0" width="100%">
	<tr><td background="img/barra.gif"  align="center"><font style="font-family: Times New Roman;" color="#FFFFFF">
			<b>  Neptune - Experiment Allocation </b></font><br/>&nbsp;
	</td></tr>
</table>


<table  border="0" cellpadding="80px" cellspacing="0" width="100%">
	<tr><td>
	
<h1 align="center">L’allocazione delle topologie</h1>
<p align="justify">
Il problema dell’allocazione delle risorse &egrave; stato affrontato applicando la tecnica del partitioning  &amp; mapping.
L’algoritmo di Lin-Kernighan risolve la fase di partitioning.
Esso fornisce un k-partizionamento del grafo che rappresenta la topologia della rete a emulare.
</p>

<p align="justify">
Tutti i nodi contenuti nello stesso sottoinsieme della partizione saranno allocati sulla medesima macchina fisica.
L’algoritmo trova  la partizione della topologia che minimizza la somma dei costi di comunicazione tra nodi virtuali
 che risiedono su macchine fisiche distinte.
I nodi che hanno maggiore necessità di banda per comunicare tra loro saranno allocati, prevalentemente, sulla stessa macchina fisica.
Mentre i nodi che non devono comunicare tra loro oppure hanno scarsa necessità di banda per comunicare saranno allocati su 
macchine fisiche distinte.
Questo meccanismo consente di ridurre l’uso della banda disponibile presso i link fisici.
 I nodi che appartengono alla stessa partizione potranno comunicare tra loro senza occupare le risorse di
  comunicazione dei link fisici ma avvalendosi dei meccanismi forniti dal kernel di XEN.
</p>

<p align="justify">
   La figura sottostante mostra un possibile bi-partizionamento di una topologia di rete costituita da 6 nodi virtuali.
</p>
<h1 align="center"><img src='img/figura27.jpg'></h1> 


<p align="justify">
Non tutte le partizioni trovate sono ammissibili.
<br> E’ necessario che la soluzione verifichi i due vincoli di ammissibilità:

</p>
<ul>
<li>Vincolo di banda;</li>
<li>Vincolo sulla capacità computazionale;</li>
</ul>
<p>
Presi due sottoinsiemi della k-partizione si verifica che tutte le comunicazioni che avvengono tra coppie di nodi appartenenti ad insiemi distinti vengono multiplate sullo stesso link fisico. Affinché  il processo di emulazione sia corretto è necessario che la somma delle bande disponibili tra  nodi che appartengono a sottoinsiemi distinti non deve eccedere la banda del corrispondente link fisico utilizzato per la loro multiplazione. Questa condizione è espressa attraverso il vincolo di banda.
Un macchina fisica può emulare un numero limitato di macchine virtuali. Questa condizione è formulata attraverso il vincolo sulla capacità computazionale. Esso pone un limite al  numero di nodi virtuali che possono essere contemporaneamente emulati sulla stessa macchina fisica.
La figura sottostante mostra un esempio di possibile allocazione di una topologia di rete.
</p>
<h1 align="center"><img src='img/figura28.jpg'></h1> 


<p align="justify">
Come si vede la rete è stata partizionata in 3 sottoinsiemi: A, B, C.<br> Le capacità di banda uscenti da ogni sottoinsieme sono le seguenti:
</p>
<ul> 
<li>La banda uscente dall’insieme A vale 2+1=3;</li>
<li>La banda uscente dall’insieme B vale 2+2=4;</li>
<li>La banda uscente dall’insieme C vale 2+1=3;</li>
</ul>
<p align="justify">
Dato che i collegamenti fisici hanno una banda disponibile di 1000 Mbit/s allora il vincolo di banda è verificato. Supponendo, inoltre, che il vincolo di capacità computazionale imponga a 3 il numero massimo di nodi virtuali da emulare sulla stessa macchina fisica allora la soluzione trovata è ammissibile e di conseguenza  può essere allocata.
La fase di partitioning termina quando viene trovato una partizionamento ammissibile ed a costo minimo della topologia di rete da emulare. Quindi si procede con la fase di mapping. Essa consiste nello stabilire le  associazioni tra le  partizioni trovate ed i nodi fisici che costituiscono il cluster. Una prima possibile soluzione a questo problema consiste nell’associare ogni partizione trovata ad una macchina fisica che non emula nessun nodo virtuale. Questa scelta garantisce un elevato livello di isolamento tra i diversi  esperimenti. Infatti non può verificarsi che sulla stessa macchina siano in esecuzione nodi virtuali che appartengono ad esperimenti distinti. Il fallimento di una macchina fisica coinvolge solo nodi di uno stesso esperimento.
</p>
<h1 align="center"><img src='img/figura29.jpg'></h1> 


<p align="justify">
Tuttavia questo approccio genera uno spreco delle risorse. In effetti si può verificare che una macchina fisica, pur emulando un certo numero di nodi virtuali di un esperimento, possiede ancora sufficienti risorse computazionali tali da garantire la corretta emulazione di ulteriori nodi virtuali che appartengono ad altri esperimenti. Inoltre l’elevato livello di isolamento offerto dall’hypervisor XEN consente l’emulazione in sicurezza, sulla stessa macchina fisica, di nodi virtuali che fanno parte di esperimenti distinti. Queste osservazioni suggeriscono l’implementazione di una procedura di mapping ottimizzata.
</p>
<br>L’algoritmo di mapping implementato si articola in 4 fasi:
<ul>
<li>Ricerca nella k-partizione del  sottoinsieme  a cardinalità minima;
<li>Ricerca di una macchina del cluster impegnata ma con sufficienti risorse computazionali residue;
<li>Associazione dell’insieme a cardinalità minima alla macchina trovata;
<li>Associazione dei restanti insiemi della k-partizione alle macchine non impegnate;
</ul>
<p align="justify">
La figura sottostante mostra un esempio di allocazione, effettuata con l’algoritmo di mapping ottimizzato, di due esperimenti. Si vuole evidenziare l’utilizzo di una stessa macchina fisica per l’emulazione di nodi che appartengono a topologie distinte.
</p>
<h1 align="center"><img src='img/figura30.jpg'  align="top" alt=""></h1> 

	</td></tr>
</table>


</body>
</html>